def fib(n):
    if n==0 or n==1:
        return n
    else:
        return fib(n-2)+fib(n-1)
def count(f):
    def counted(n):
        counted.call_count +=1
        return f(n)
    counted.call_count = 0
    return counted
def memo(f):
    cache={}
    def memoized(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return memoized
fib = count(fib)
counted_fib =fib
fib = memo(fib)
fib = count(fib)
print(fib(30))
print("origin:", fib.call_count, "memorized:", counted_fib.call_count)

%matplotlib inline
import matplotlib.pyplot as plt
plt.style.use('ggplot')
plt.rc('font', size = 16)

from timeit import repeat
from numpy import median, percentile

def plot_times(name, xs, n=15):
    f = lambda x: name+'('+str(x)+')'
    g = globals()

    samples = []
    for _ in range(n):
        times = lambda x: repeat(f(x), globals = g, number = 1, repeat = n)
        samples.append([median(times(x)) for x in xs])
    ys = [10e3*median(sample) for sample in zip(*samples)]

    plt.figure(figsize=(8, 8))
    plt.plot(xs, ys)
    plt.xlabel('n')
    plt.ylabel('ms')

def exp_fast(b,n):
    if n==0:
        return 1
    elif n%2==0:
        return square(exp_fast(b,n//2))
    else:
        return b*exp_fast(b, n-1)

def square(x):
    return x*x

exp_2_fast = lambda n: exp_fast(2.0, n)
plot_times('exp_2_fast', range(20, 1600, 10))